import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;

/*
 * @lc app=leetcode.cn id=922 lang=java
 *
 * [922] 按奇偶排序数组 II
 *
 * https://leetcode-cn.com/problems/sort-array-by-parity-ii/description/
 *
 * algorithms
 * Easy (66.41%)
 * Likes:    69
 * Dislikes: 0
 * Total Accepted:    21.1K
 * Total Submissions: 31.7K
 * Testcase Example:  '[4,2,5,7]'
 *
 * 给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
 *
 * 对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
 *
 * 你可以返回任何满足上述条件的数组作为答案。
 *
 *
 *
 * 示例：
 *
 * 输入：[4,2,5,7]
 * 输出：[4,5,2,7]
 * 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
 *
 *
 *
 *
 * 提示：
 *
 *
 * 2 <= A.length <= 20000
 * A.length % 2 == 0
 * 0 <= A[i] <= 1000
 *
 *
 *
 *[4,1,1,0,1,0]
 */

// @lc code=start
class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int odd = 1, even = 0;
        while(odd < A.length && even < A.length) {
            while(odd < A.length && A[odd] % 2 != 0)
                odd += 2;
            while(even < A.length && A[even] % 2 == 0)
                even += 2;
            if(odd < A.length && even < A.length) {
                int a = A[odd];
                A[odd] = A[even];
                A[even] = a;
            }
        }
        return A;
    }
}
// @lc code=end

